package practice_2025_7_22;

import java.util.*;

class Solution {
    /**
     * 课程表
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses]; // 入度
        Map<Integer, List<Integer>> hash = new HashMap<>(); // 与元素相连的点
        for(int i = 0; i < prerequisites.length; i++) {
            int prev = prerequisites[i][1];
            int next = prerequisites[i][0];
            in[next]++;
            List<Integer> list = hash.getOrDefault(prev, new ArrayList<>());
            list.add(next);
            hash.put(prev, list);
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < in.length; i++) {
            if (in[i] <= 0) {
                queue.add(i);
            }
        }
        if (queue.isEmpty()) {
         //   System.out.println(" return");
            return false;
        }
        List<Integer> res = new ArrayList<>();
        while(!queue.isEmpty()) {
            int k = queue.poll();
            res.add(k);
            if (hash.containsKey(k)) {
                List<Integer> nexts = hash.get(k);
                for(int i = 0; i < nexts.size(); i++) {
                    int next = nexts.get(i);
                    in[next]--;
                    // System.out.println("next: " + next + " in: " + in[next]);
                    // System.out.println(" k: " + k);
                    if (in[next] <= 0) {
                        queue.add(next);
                    }
                }
            }
        }
      //  System.out.println(" size: " + res.size() + " res: " + res.toString());
        return res.size() >= numCourses;
    }

    /**
     * 课程表2
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses]; // 入度
        Map<Integer, List<Integer>> hash = new HashMap<>(); // 与元素相连的点
        for(int i = 0; i < prerequisites.length; i++) {
            int prev = prerequisites[i][1];
            int next = prerequisites[i][0];
            in[next]++;
            List<Integer> list = hash.getOrDefault(prev, new ArrayList<>());
            list.add(next);
            hash.put(prev, list);
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < in.length; i++) {
            if (in[i] <= 0) {
                queue.add(i);
            }
        }
        int[] res = new int[numCourses];
        int j = 0;
        if (queue.isEmpty()) {
            //   System.out.println(" return");
            return new int[]{};
        }
        while(!queue.isEmpty()) {
            int k = queue.poll();
            res[j++] = k;
            if (hash.containsKey(k)) {
                List<Integer> nexts = hash.get(k);
                for(int i = 0; i < nexts.size(); i++) {
                    int next = nexts.get(i);
                    in[next]--;
                    // System.out.println("next: " + next + " in: " + in[next]);
                    // System.out.println(" k: " + k);
                    if (in[next] <= 0) {
                        queue.add(next);
                    }
                }
            }
        }
        //  System.out.println(" size: " + res.size() + " res: " + res.toString());
        if (j < numCourses - 1) {
            return new int[]{};
        } else {
            return res;
        }
    }

    /**
     * 火星词典
     * @param words
     * @return
     */
    public String alienOrder(String[] words) {
        // 还原出已知字母顺序
        // c -> b
        // b -> z
        // c -> b
        //
        // wertf
        Map<Character, Integer> in = new HashMap<>(); // 入度
        Map<Character, HashSet<Character>> edges = new HashMap<>(); // 邻接表
        // 初始化
        for(String s: words) {
            for(int i = 0; i < s.length(); i++) {
                in.put(s.charAt(i), 0);
            }
        }
        // 计算入度 + 填写邻接表
        for(int i = 0; i < words.length; i++) {
            for(int j = i + 1; j < words.length; j++) {
                String prev = words[i];
                String next = words[j];
                int cur = 0;
                while(cur < prev.length() && cur < next.length()) {
                    char ch1 = prev.charAt(cur);
                    char ch2 = next.charAt(cur);
                    if (ch1 != ch2) {
                        HashSet<Character> set = edges.getOrDefault(ch1, new HashSet<Character>());
                        if (!set.contains(ch2)) {
                            set.add(ch2);
                            edges.put(ch1, set);
                            in.put(ch2, in.getOrDefault(ch2, 0) + 1);
                        }

                        break;
                    } else {
                        cur++;
                    }
                }
                if (cur >= next.length() && cur < prev.length()) {
                    return "";
                }
            }
        }
        // c -> b
        // a -> z
        // a -> b
        //
        // bfs 进行拓扑排序
        StringBuilder res = new StringBuilder();
        Queue<Character> queue = new LinkedList<>();
        for(char ch: in.keySet()) {
            if (in.get(ch) == 0) {
                queue.add(ch);
            }
        }
        while(!queue.isEmpty()) {
            char ch = queue.poll();
            res.append(ch);
            if (edges.containsKey(ch)) {
                Set<Character> set = edges.get(ch);
                for(char next: set) {
                    in.put(next, in.getOrDefault(next, 0) - 1);
                    if (in.get(next) == 0) {
                        queue.add(next);
                    }
                }
            }
        }
        // System.out.println("res: " + res);
        for(char ch: in.keySet()) {
            if (in.get(ch) > 0) {
                // System.out.println("val: " + in.get(ch));
                return "";
            }
        }
        return res.toString();
    }
}